/*
Merge.
Se tiene un determinado número de archivos
(particiones) ordenados por la misma clave. Se
quiere obtener un único archivo ordenado por la
clave.
Merge Balanceado N-Vías.
Se pueden tener N archivos abiertos, se usan N/2
archivos de Output y el resto de Input. Si N es
impar la cantidad de archivos de Input es mayor
que la de Output en uno.
Ejemplo:
N = 6, Cantidad de particiones: 13.
Input 1 P01 P04 P07 P10 P13
P01-09
Input 2 P02 P05 P08 P11
P10-13
Input 3 P02 P06 P09 P12
Output 1
P01-03 P10-12
P01-13
Output 2
P04-06 P13
Output 3
P07-09
Una partición se lee múltiples veces.
Optimal Merge.
Mantiene una lista ordenada de todas las particiones
según el tamaño de la partición. Se pueden tener
abiertos N archivos. Se toman las N – 1 particiones
de menor tamaño para Input y 1 partición de Output.
Las particiones pequeñas son las que van a ser leídas
más de una vez (de ser necesario), y se deja las
particiones de mayor tamaño para el final.
Ejemplo:
N = 3, Cantidad de particiones: 6
Long.
10 8
5
3
1
1
2
5
10
18
28
Ventajas:
Al tener en cuenta las longitudes se leen
menos registros.
Desventajas:
Mantenimiento de la lista.
Merge Polifásico.
Se pueden tener abiertos N archivos. Se toman N – 1
particiones para Input y 1 partición de Output. La
cantidad de particiones tiene que pertenecer a la serie de
Fibonacci de orden N-1
Particiones Dummy (Para llevar el número de
particiones a un elemento de la serie de Fibonacci).
Para 32 particiones de tamaño n (4 vías): 57-32 = 25
dummies.
f(3) = 1 1 1 3 5 9 17 31 57
1
3
5
9
17
31
57
0
1
2
4
0
7
20
0
1
2
0
4
11
24
0
1
0
2
6
13
0
1
0
1
3
7
0
13
13*2n + 4*3n
Lecturas: 7*2n
1*3n + 1*5n + 2*6n
1*8n + 1*10n
1*16n
1*32n
One Way Merge.
Todas las particiones (con sus datos ordenados) están
grabadas en un mismo archivo.
Se cuenta con la información de donde comienza y donde
termina cada partición.
Se realiza el mismo procedimiento de un merge
convencional pero tomando los registros de un mismo
archivo en lugar de muchos.
Se usa con archivos relativos o streams y solo requiere 2
vias (una de entrada y una de salida)
Partición 1
Archivo
Partición 2
Partición 3
Partición 4
Ordenado

 */

#include <stdio.h>
#include <stdlib.h>

/*
 * Simple C Test Suite
 */

void setup() {
    printf("mergeTest test 1\n");
}

void test2() {
    printf("mergeTest test 2\n");
    printf("%%TEST_FAILED%% time=0 testname=test2 (mergeTest) message=error message sample\n");
}

int main(int argc, char** argv) {
    printf("%%SUITE_STARTING%% mergeTest\n");
    printf("%%SUITE_STARTED%%\n");

    printf("%%TEST_STARTED%% test1 (mergeTest)\n");
    setup();
    printf("%%TEST_FINISHED%% time=0 test1 (mergeTest) \n");

    printf("%%TEST_STARTED%% test2 (mergeTest)\n");
    test2();
    printf("%%TEST_FINISHED%% time=0 test2 (mergeTest) \n");

    printf("%%SUITE_FINISHED%% time=0\n");

    return (EXIT_SUCCESS);
}
